<?php

// Class for a node inside a Binary Tree
class CBTNode {
	var $value;
	var $left;
	var $right;

	function __construct(){
		$this->value = null;
		$this->left = null;
		$this->right = null;
	}
}
// ------------------------------------------------------
// Functions for a binary search tree
// ------------------------------------------------------
function bst_insert( $value, $root ){

	if( !$root ){
		// Create a new root with the value
		$node = new CBTNode();
		$node->value = $value;
		return $node;
	}

	if( $value < $root->value ){
		$root->left = bst_insert($value, $root->left);
	}
	else {
		$root->right = bst_insert($value, $root->right);
	}

	return $root;
}

function bst_generate( $min, $max, $size ){
	if( $max <= $min || $size <= 0 ){
		return null;
	}

	$root = null;

	for( $index=0; $index<$size; $index++ ){
		$value = rand($min, $max);
		$root = bst_insert($value, $root);
	}

	return $root;
}

// ------------------------------------------------------
// Functions for a random binary tree
// ------------------------------------------------------
function bt_insert( $value, $root ){
	if( !$root ){
		// Create a new root with the value
		$node = new CBTNode();
		$node->value = $value;
		return $node;
	}

	// A binary tree with random insertion to left or right
	$isLeft = (rand(0, 100) % 2);
	if( $isLeft ){
		$root->left = bst_insert($value, $root->left);
	}
	else {
		$root->right = bst_insert($value, $root->right);
	}

	return $root;
}

function bt_generate( $min, $max, $size ){
	if( $max <= $min || $size <= 0 ){
		return null;
	}

	$root = null;

	for( $index=0; $index<$size; $index++ ){
		$value = rand($min, $max);
		$root = bt_insert($value, $root);
	}

	return $root;
}

// ------------------------------------------------------
// Functions shared for any binary trees
// ------------------------------------------------------
function bt_print_inorder( $root ){
	if( !$root ){
		return;
	}

	if( $root->left ){
		bt_print_inorder( $root->left );
	}

	echo "{$root->value}   ";

	if( $root->right ){
		bt_print_inorder( $root->right );
	}
}

function bt_print_preorder( $root ){
	if( !$root ){
		return;
	}

	echo "{$root->value}   ";

	if( $root->left ){
		bt_print_preorder( $root->left );
	}

	if( $root->right ){
		bt_print_preorder( $root->right );
	}	
}

function bt_print_postorder( $root ){
	if( !$root ){
		return;
	}
	
	if( $root->left ){
		bt_print_postorder( $root->left );
	}

	if( $root->right ){
		bt_print_postorder( $root->right );
	}

	echo "{$root->value}   ";	
}

function bt_implode_inorder( $root ){
	if( !$root ){
		return ' ';	
	} 

	$result = '';
	if( $root->left ){
		$result .= bt_implode_inorder( $root->left );
	}
	$result .= ($root->value .' ');
	if( $root->right ){ 
		$result .= bt_implode_inorder( $root->right );
	}
	return $result;
}

function bt_implode_preorder( $root ){
	if( !$root ){
		return ' ';	
	} 

	$result = '';
	$result .= ($root->value .' ');
	if( $root->left ){
		$result .= bt_implode_preorder( $root->left );
	}
	if( $root->right ){ 
		$result .= bt_implode_preorder( $root->right );
	}
	return $result;
}

function bt_implode_postorder( $root ){
	if( !$root ){
		return ' ';	
	} 

	$result = '';
	if( $root->left ){
		$result .= bt_implode_postorder( $root->left );
	}
	if( $root->right ){ 
		$result .= bt_implode_postorder( $root->right );
	}
	$result .= ($root->value .' ');
	return $result;
}

function bt_draw( $root ){
	if( !$root ){
		return;
	}

	// BST height to determine the dimension
	$height = bst_height( $root );

	// A random id
	$id = "bst_canvas_".rand(1, 100);
	echo "<div class='bst_container' style='border:solid 1px; width: 500px; height: 300px'>";
	echo "<div class='bst_canvas' id='$id' style='position:absolute;'>";
	echo <<<EOD
	<script type='text/javascript'>
	var jg = new jsGraphics("$id");
	function drawNode( value, x, y ){
		jg.setColor("#000000");
		jg.drawRect( x, y, 20, 15 );

		jg.drawStringRect( value, x, y, 20, "left");
		jg.paint();
	}
EOD;

	$offset = 5 * pow( 2, $height - 1 );
	
	bt_draw_recursive($root, 250, 10, $offset);

	echo "</script>";
	echo "</div>"; // bst_canvas
	echo "</div>"; // bst_container
}

function bt_draw_recursive( $root, $x, $y, $offset ){
	if( !$root ){
		return;
	}

	// Draw
	echo "drawNode({$root->value}, $x, $y);";

	$offsetY = 30;

	// Draw left
	if( $root->left ){
		$newX = $x - $offset;
		echo "jg.drawLine($x, $y, $newX, $y+$offsetY);";
		bt_draw_recursive( $root->left, $newX, $y+$offsetY, ($offset / 2) );
	}
	// Draw right
	if( $root->right ){
		$newX = $x + $offset;
		echo "jg.drawLine($x, $y, $newX, $y+$offsetY);";
		bt_draw_recursive( $root->right, $newX, $y+$offsetY, ($offset / 2) );
	}
}

function bst_height( $root ){
	if( !$root ){
		return 0;
	}

	$height_left = bst_height( $root->left );
	$height_right = bst_height( $root->right );

	return 1 + max( $height_left, $height_right );
}